
const testWeightBagProblem = function(weight,value,size){
  // 传入的参数是重量数组 价值数组 和 背包容量限制
  const len = weight.length // 获得重量数组的长度 也就是待选择商品的个数
  let dp = new Array(len).fill().map(()=>Array(size+1).fill(0)) // 初始化dp数组 也就是初始化物品个数 和 背包容量的数组 其中背包容量是size+1 是为了保证容量能到size 例如size = 4 那么这个数组就是0,1,2,3,4
  // dp[i][j]的含义是0~i的物品任意选取 放入容量为j的背包的最大价值
  // 初始化 找到按照物品重量升序排列的第一个物品 将其加入到dp数组中 也就是容量为weight[0]的位置他的值就是这个物品的价值
  for(let j = weight[0];j<=size;j++){
    dp[0][j] = value[0]
  }
  // weight数组的长度就是物品个数len
  for(let i = 1;i < len;i++){
    // 遍历物品的个数
    for(let j = 0;j <=size;j++){
      // 遍历背包容量
      if(j < weight[i]) {
        // 如果这个背包容量小于这个物品的重量 说明dp[i][j] 就是dp[i-1][j] 这个背包的最大价值就是没有这个物品的最大价值 就是0-i-1的物品随机选取 放入背包容量为j的最大价值 因为这个的容量小于这个物品的重量 所以 还是等于dp[i-1][j]
        dp[i][j] = dp[i-1][j]
      }else{
        // 如果这个背包的容量大于等于这个物品的价值 那么这个背包的能装的最大价值就是 不装这个物品的价值 和 装这个物品的价值的最大值 因为装这个物品 就需要有这么大的空间 所以 装这个物品的价值就是 dp[i-1][j-weight[i]] 不装这个物品且有这么多容量的价值 +value[i] 这个物品的价值
        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
      }
    }
  }
  // 打印这个dp数组
  console.table(dp);
  return dp[len-1][size]
}
console.log(testWeightBagProblem([1,3,4,5],[15,20,30,55],6));
